Jerry's Log

Hierholzer's Algorithm

Posted: 2025-12-03 Tags: cs algorithm

contents

히어홀저 알고리즘(Hierholzer's Algorithm) 은 그래프에서 오일러 회로(Eulerian Circuit)(또는 오일러 사이클)를 찾는 효율적인 방법입니다.

오일러 회로란 유한 그래프의 모든 간선(edge) 을 정확히 한 번씩 방문하고, 시작했던 정점에서 끝나는 경로를 말합니다.

플뢰리 알고리즘(Fleury's Algorithm)과 같은 단순한 접근 방식은 느릴 수 있지만($O(E^2)$), 히어홀저 알고리즘은 선형 시간($O(E)$) 에 실행되므로 이 문제에 대한 표준 솔루션(Gold standard)으로 여겨집니다.

1. 전제 조건: 언제 작동하는가?

알고리즘을 실행하기 전에 오일러 회로가 실제로 존재하는지 확인해야 합니다. 그 조건은 그래프의 종류에 따라 다릅니다.

  1. 무방향 그래프 (Undirected Graph):
    • 그래프가 연결되어 있어야 합니다 (간선이 있는 모든 정점이 하나의 연결 요소에 속해야 함).
    • 모든 정점의 차수(Degree)가 짝수여야 합니다. (차수 = 연결된 간선의 수).
  2. 방향 그래프 (Directed Graph):
    • 그래프가 강하게 연결(Strongly Connected)되어 있어야 합니다.
    • 모든 정점에 대해 진입 차수(In-degree)와 진출 차수(Out-degree)가 같아야 합니다.

이 조건들이 충족되지 않으면 히어홀저 알고리즘은 실패하거나 잘못된 결과를 생성합니다.

2. 핵심 개념: 사이클 꿰매기 (Stitching Cycles) 🧵

히어홀저 알고리즘의 직관은 간단합니다. "오일러 회로는 서로 분리된 사이클들을 하나로 합친(병합한) 것이다."

한 노드에서 걷기를 시작한다고 상상해 보세요. 모든 노드의 차수가 짝수이기 때문에, 어떤 노드에 들어갈 때마다 그곳을 떠날 수 있는 사용하지 않은 간선이 반드시 존재합니다. 결국, 당신은 반드시 시작 노드로 돌아오게 됩니다. 이렇게 하나의 사이클을 찾았습니다.

하지만 이 사이클이 그래프의 모든 간선을 포함하지 않을 수도 있습니다. 현재 사이클에 포함된 노드 중 아직 사용하지 않은 간선이 연결된 노드가 있을 수 있습니다.

  1. 그런 노드에서 잠시 멈춥니다.
  2. 그 노드에서 새로운 "우회로"(서브 사이클)를 시작합니다.
  3. 우회로가 다시 그 노드로 돌아오면, 이 우회로를 메인 경로에 병합(연결)합니다.

3. 알고리즘 (단계별 설명)

"사이클 병합" 개념은 이론을 설명하지만, 실제 구현은 보통 두 개의 스택 (또는 스택 하나와 리스트 하나)을 사용하는 깊이 우선 탐색(DFS) 접근 방식을 사용합니다.

자료 구조:

단계:

  1. 시작: 임의의 시작 정점 v를 선택하여 Current Path 스택에 넣습니다.
  2. 루프: Current Path가 비어있지 않은 동안 반복합니다:
    • Current Path 스택의 맨 위에 있는 정점 u를 봅니다.
    • Case A (간선이 남은 경우): u에게 아직 사용하지 않은 나가는 간선이 있다면:
      • 이웃 정점 v를 선택합니다.
      • 그래프에서 간선 u-v를 제거합니다 (사용됨으로 표시).
      • v를 Current Path 스택에 넣습니다. (앞으로 전진).
    • Case B (막힌 경우): u에게 사용하지 않은 나가는 간선이 없다면:
      • 이는 u에서 끝나는 사이클이나 경로의 일부를 완료했음을 의미합니다.
      • Current Path에서 u를 꺼냅니다(Pop).
      • u를 Circuit 리스트에 추가합니다. (백트래킹).
  3. 결과: Current Path 스택이 비게 되면, Circuit 리스트에 오일러 경로가 담깁니다. 단, 리스트는 역순으로 채워지므로(끝에서 시작으로), 필요하다면 뒤집어야 합니다.

4. 상세 예제 🔍

다음 그래프로 추적해 보겠습니다.

정점: 0, 1, 2, 3, 4 간선:

시각화: 삼각형(0-1-2)과 또 다른 삼각형(1-3-4)이 노드 1에서 만나는 형태입니다. 모든 정점은 짝수 차수를 가집니다 (0:2, 1:4, 2:2, 3:2, 4:2).

실행 과정:

  1. 0에서 시작.
    • curr_path: [0]
    • circuit: []
  2. 0은 이웃 1이 있음. 1로 이동. 간선 0-1 제거.
    • curr_path: [0, 1]
  3. 1은 이웃 2가 있음. 2로 이동. 간선 1-2 제거.
    • curr_path: [0, 1, 2]
  4. 2는 이웃 0이 있음. 0으로 이동. 간선 2-0 제거.
    • curr_path: [0, 1, 2, 0]
  5. 0은 남은 이웃이 없음. (막힘!). 0을 꺼내서(Pop) 회로에 추가.
    • curr_path: [0, 1, 2]
    • circuit: [0]
  6. 2는 남은 이웃이 없음. 2를 꺼내서 회로에 추가.
    • curr_path: [0, 1]
    • circuit: [0, 2]
  7. 1은 이웃(3, 4)이 있음. (교차점으로 돌아옴). 3을 선택. 간선 1-3 제거.
    • curr_path: [0, 1, 3]
  8. 3은 이웃 4가 있음. 4로 이동. 간선 3-4 제거.
    • curr_path: [0, 1, 3, 4]
  9. 4는 이웃 1이 있음. 1로 이동. 간선 4-1 제거.
    • curr_path: [0, 1, 3, 4, 1]
  10. 1은 남은 이웃이 없음. (4개 간선 모두 사용됨). 1을 꺼냄.
    • curr_path: [0, 1, 3, 4]
    • circuit: [0, 2, 1]
  11. 4는 남은 이웃이 없음. 4를 꺼냄.
    • circuit: [0, 2, 1, 4]
  12. 3은 남은 이웃이 없음. 3을 꺼냄.
    • circuit: [0, 2, 1, 4, 3]
  13. 1은 남은 이웃이 없음. 1을 꺼냄.
    • circuit: [0, 2, 1, 4, 3, 1]
  14. 0은 남은 이웃이 없음. 0을 꺼냄.
    • circuit: [0, 2, 1, 4, 3, 1, 0]

최종 회로 (뒤집음): 0 -> 1 -> 3 -> 4 -> 1 -> 2 -> 0. 모든 간선을 정확히 한 번씩 방문했습니다.

5. 왜 효율적인가? (복잡도)

6. 코드 구현 (Python)

다음은 방향 그래프에 대한 깔끔한 구현입니다 (그래프가 오일러 회로 조건을 만족한다고 가정).

from collections import defaultdict

def findEulerianCircuit(graph):
    # 그래프는 리스트의 딕셔너리 형태: { u: [v1, v2, ...] }
    
    # 여기서 그래프 유효성(차수 등)을 검사할 수 있습니다.
    # 이 스니펫에서는 입력이 유효하다고 가정합니다.

    stack = []
    circuit = []
    
    # 간선이 있는 임의의 노드에서 시작
    curr_node = 0 
    stack.append(curr_node)
    
    while stack:
        # 스택의 맨 위 노드 확인
        u = stack[-1]
        
        # u에게 사용 가능한 간선이 있다면
        if graph[u]:
            # 마지막 간선을 선택 (pop은 O(1) 효율성)
            v = graph[u].pop()
            stack.append(v)
        else:
            # 남은 간선이 없음, 백트래킹하며 회로에 추가
            circuit.append(stack.pop())
            
    # 회로는 역순으로 만들어지므로 뒤집어서 반환
    return circuit[::-1]

# 사용 예시
# 0->1, 1->2, 2->0, 1->3, 3->4, 4->1
g = defaultdict(list)
g[0] = [1]
g[1] = [2, 3]
g[2] = [0]
g[3] = [4]
g[4] = [1]

print(findEulerianCircuit(g))
# 출력: [0, 1, 3, 4, 1, 2, 0] (또는 유사한 순열)

요약

히어홀저 알고리즘은 오일러 회로를 찾는 최적의 방법입니다. 막힐 때까지(사이클 형성) 경로를 무작정 따라가다가, 막히면 백트래킹을 하면서 사용하지 않은 간선이 있는 노드를 찾아 서브 사이클을 시작하고, 결국 이들을 하나의 연속적인 루프로 꿰매는 방식으로 작동합니다.

references

Related Posts